1. Field of the Invention
The present invention relates to wireless devices, such as radio-frequency identification (RFID) tags, and, in particular, to methods of quickly estimating the cardinality of a set of wireless devices. i.e. the number of devices in the set.
2. Description of the Related Art
A common problem that arises in any RFID deployment is the quick estimation of the number of tags in a field, up to a desired level of accuracy. Prior work in this area has focused on the identification of tags, which takes a relatively long time and is unsuitable for many situations, especially if the tag set is dense or highly dynamic.
Radio-frequency identification (RFID) tags are being used in diverse applications in everyday scenarios, ranging from inventory control and tracking to medical-patient management, and are appearing ubiquitously in increasingly-large numbers. The key driver behind this widespread adoption is the simplicity of the tags, which enables relatively low (nearly zero) cost at high volumes. The tags themselves vary significantly in their capabilities, from “dumb” or passive tags that merely transmit a particular bit-string when probed by a reader, to “smart” or active tags that have their own CPUs, memories, and power supplies. Passive tags are designed to have a relatively long life and, hence, do not use any on-board energy sources for transmitting data. Rather, they derive the energy needed for transmission from a probe signal sent by a reader node. This probe signal can be transmitted, e.g., via magnetic coupling (called near-field), or electro-magnetic coupling (called far-field). The latter has a much larger range and is designed to read hundreds of tags at a time, while the former typically has a range of less than 1 meter and, hence, is used to read less than 1 to 5 tags at a time.
RFID tags can be generally classified into passive tags, semi-passive tags, and active tags. Active and semi-passive tags have their own power sources, typically in the form of batteries. However, semi-passive tags do not use their power source for transmission, but instead use it primarily to drive other on-board circuitry. Nearly all current RFID deployments around the world involve passive and semi-passive tags. A sensor mote (a wireless transceiver that is also a remote sensor) can be classified as being an active tag.
RFID tags are often used to label items. Hence, identifying these items is normally the main goal of such an RFID system. The general idea is as follows: the reader probes a set of tags, and the tags reply back. There are many algorithms that enable identification, which can be classified into two categories: probabilistic and deterministic. Since RFID devices are relatively simple and operate in a wireless medium, collisions will typically result whenever a reader probes a set of tags. The identification algorithms use anti-collision schemes to resolve such collisions.
In probabilistic-identification algorithms, a framed scheme dubbed an “ALOHA” scheme is used, as fully described in F. C. Schoute, “Dynamic framed length ALOHA,” IEEE Transactions on Communications, vol. 31(4). April 1983, the disclosure of which is incorporated herein in its entirety. In an ALOHA scheme, the reader communicates the frame length, and the tags pick a particular slot in the frame in which to transmit. The reader repeats this process until all tags have transmitted at least once successfully in a slot without collisions. In semi-passive and active tag systems, the reader can acknowledge tags that have succeeded at the end of each frame. Hence, those tags can stay silent in subsequent frames, reducing the probability of collisions, thereby shortening the overall identification time. In passive tag systems, all tags will continue to transmit in every frame, which lengthens the total the it takes to identify all tags.
Deterministic identification algorithms typically use a slotted-ALOHA model, where the reader identifies the set of tags that will transmit in a given slot and tries to reduce the contending tag set in the next slot based on the result in the previous slot. These algorithms fall into the class of “tree-based” identification algorithms, with the tags classified on a binary tree based on their IDs, and the reader moving down the tree at each step to identify all nodes. Deterministic algorithms are typically faster than probabilistic schemes in terms of actual tag-response slots used. However, such algorithms suffer from large reader overhead, since the reader has to specify address ranges to isolate contending tag subsets using a probe at the beginning of each slot. The common requirement for both classes of identification algorithms is an estimate of t, the actual number of tags in the system. This estimate is used to set the optimal frame size in framed ALOHA and to guide the tree-based identification process for computing the expected number of slots needed for identification. Hence, it is important to have a quick estimate that is as accurate as possible. The estimation and identification steps could hypothetically be combined or be performed concurrently, to save time, e.g., in probabilistic-identification algorithms. However, the drawback is that the initial steps then rely on inaccurate estimates of the number of tags. Hence, the estimation process should be able to use non-identifiable information, such as a string of bits used by all tags, to compute the size of the tag set t.
Estimation of the cardinality of the tag set is also important in other problems pertaining to RFID tags. Due to privacy constraints, it might not be acceptable for readers to query the tags for their identification in certain instances. In such instances, tags could send out non-identifiable information, which could still be used to compute estimates of cardinality. Another set of problems arises when the tag set is changing so fast that identification of all tags is impossible (e.g., an airplane flying over a field of sensors while trying to obtain an estimate of the number of active sensors remaining in the field). An efficient cardinality estimation scheme should be able to work in such environments as well. It should be noted that, in these instances, using an active tag does not confer any special advantages to the estimation problem from an energy-management perspective, as opposed to using a passive tag.